import java.math.BigInteger;


public class Fraction {
	public final BigInteger num;
	public final BigInteger den;
	
	public Fraction(long num, long den) {
		this(BigInteger.valueOf(num), BigInteger.valueOf(den));
	}
	
	public Fraction(BigInteger num, BigInteger den) {
		if (den.signum() < 0) {
			den = den.negate();
			num = num.negate();
		}
		BigInteger gcd = num.gcd(den);
		this.num = num.divide(gcd);
		this.den = den.divide(gcd);
	}
	
	public Fraction add(Fraction that) {
		BigInteger newNum = num.multiply(that.den).add(that.num.multiply(den));
		BigInteger newDen = den.multiply(that.den);		
		
		return new Fraction(newNum, newDen);
	}
	
	public Fraction multiply(Fraction that) {
		return new Fraction(num.multiply(that.num), den.multiply(that.den));
	}
	
	public Fraction inverse() {
		return new Fraction(den, num);
	}
	
	public int log2up() {
		BigInteger[] divmod = num.divideAndRemainder(den);
		if (divmod[0].compareTo(BigInteger.ONE) < 0) {
			throw new AssertionError();
		}
		if (divmod[0].bitCount() == 1 && divmod[1].signum() == 0) {
			return divmod[0].bitLength() - 1;
		} else {
			return divmod[0].bitLength();
		}
	}
	
	public BigInteger nBitsAfterComma(int nBits) {
		BigInteger mod = num.remainder(den);
		mod = mod.shiftLeft(nBits);
		return mod.divide(den);
	}
	
	public String toString() {
        if (num.signum() == 0) {
            return "0";
        }
        BigInteger powered = num;
        int offset = 0;
        while (powered.divide(den).toString().length() < 8) {
            offset++;
            powered = powered.multiply(BigInteger.TEN);
        }
        offset -= 7;
        String z = powered.divide(den).toString();
        String rv =  "$" + z.charAt(0) + "." + z.substring(1);
        if (offset != 0) {
            rv += "\\times 10^{" + (-offset) + "}$";
        } else {
        	rv += "$";
        }

        return rv;
	}
}
